package simpleSort;

/**
 * 插入排序算法 特性 平均时间复杂度 n方 ，对有升序的数组 n  擅长处理近乎有序的数组
 */
public class InsertSort {

    // arr[0,i) 有序  arr[i,n)未排序
    public static <E extends Comparable<E>> void sort(E[] arr) {
//        for (int i = 1; i < arr.length; i++) {
//            int compareIndex = i;
//            for (int j = i - 1; j >= 0; j--) {
//                if (arr[j].compareTo(arr[compareIndex]) > 0) {
//                    ArrTools.swap(arr,compareIndex, j);
//                    compareIndex = j;
//                }else
//                    break;
//            }
//        }


//        for (int i = 0; i < arr.length; i++) {
//            for (int j = i; j - 1 >= 0 && arr[j].compareTo(arr[j-1]) < 0; j--) {
//                ArrTools.swap(arr, j, j - 1);
//            }
//        }

        for (int i = 0; i < arr.length; i++) {
            E t = arr[i];
            int j = i;
            for (; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        // arr[0,i) 局部有序 ， 数组的 arr[0,i) 是排序过的，排序是从1开始的
        // arr[i,n) 位排序
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int j;
            E t = arr[i];
            // arr[i] 的元素和 [0,i)上的元素依次对比
            for (j = i; j - 1 >= 0 && t.compareTo(arr[j - 1]) < 0; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = t;
        }
    }

    /**
     * 循环不变量为：arr[0,i) 未排序  arr[i,n) 局部i 到 n 的数据是排序
     *
     * @param arr
     * @param <E>
     */
    public static <E extends Comparable<E>> void descSort(E[] arr) {
        int n = arr.length;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i; j+1 < n; j++) {
                if (arr[j].compareTo(arr[j+1]) > 0){
                   ArrTools.swap(arr,j+1,j);
                }else {
                    break;
                }
            }
        }
    }
}
